Piggybacking on Merge Sort
To solve this in $O(N \log N)$, we'll modify the standard Merge Sort algorithm. The total number of inversions can be broken down recursively:
The core idea is that during the merge step, when we compare elements from the sorted `left` and `right` halves, we gain valuable information. If we take an element from the `right` half because it's smaller than the current element in the `left` half, this `right` element has effectively "jumped over" all remaining elements in the `left` half. Since the `left` half is already sorted, we know all its remaining elements are larger, and thus we can count a batch of inversions at once.
1. Divide & Recurse
Split the list into a `left` and `right` half. The total inversions will be the sum of inversions from the `left` half, the `right` half, and the inversions *between* the two halves.
2. Conquer & Count
This is the key step. While merging the two sorted halves, we can efficiently count the "split inversions"—pairs where one element is in the left half and the other is in the right.